//给出一个含有不重复整数元素的数组 arr ，每个整数 arr[i] 均大于 1。 
//
// 用这些整数来构建二叉树，每个整数可以使用任意次数。其中：每个非叶结点的值应等于它的两个子结点的值的乘积。 
//
// 满足条件的二叉树一共有多少个？答案可能很大，返回 对 10⁹ + 7 取余 的结果。 
//
// 
//
// 示例 1: 
//
// 
//输入: arr = [2, 4]
//输出: 3
//解释: 可以得到这些二叉树: [2], [4], [4, 2, 2] 
//
// 示例 2: 
//
// 
//输入: arr = [2, 4, 5, 10]
//输出: 7
//解释: 可以得到这些二叉树: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2]. 
//
// 
//
// 提示： 
//
// 
// 1 <= arr.length <= 1000 
// 2 <= arr[i] <= 10⁹ 
// arr 中的所有值 互不相同 
// 
//
// Related Topics 数组 哈希表 动态规划 排序 👍 213 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author ldltd
 * @date 2023-09-02 21:36:16
 * @description 823.带因子的二叉树
 */
public class BinaryTreesWithFactors{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new BinaryTreesWithFactors().new Solution();
		  int []arr={2,4,8};
		 System.out.println(solution.numFactoredBinaryTrees(arr));
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int numFactoredBinaryTrees(int[] arr) {
		int res=0,mod = 1000000007;
		int n = arr.length;
//	逆序
//		arr= IntStream.of(arr)
//				.boxed()
//				.sorted(Comparator.reverseOrder())
//				.mapToInt(Integer::intValue)
//				.toArray();
		long []dp=new long[n];
		Arrays.sort(arr);
		Map<Integer,Integer> map=new HashMap<>();
		//比如 2 4 8 16
		for (int i = 0; i < n; i++) {
			dp[i]=1;
			for (int j=0; arr[j]*arr[j] <=arr[i]; j++) {
				//比如 16 4 4
				if(arr[i]==arr[j]*arr[j]){
					dp[i]=(dp[i]+(dp[j]*dp[j])%mod)%mod;
					//比如 16 2 8,能除尽，且包含另一个因子
				}else if(arr[i]%arr[j]==0&&map.containsKey(arr[i]/arr[j])){
					int k = map.get(arr[i] / arr[j]);
					dp[i]=(dp[i]+((dp[k]*dp[j]*2)%mod))%mod;
				}
			}
			map.put(arr[i],i);
			res = (int) ((res + dp[i])%mod);
		}
		return  res;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
